{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Binary Trees With Factors"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #hash-table #dynamic-programming #sorting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #哈希表 #动态规划 #排序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: numFactoredBinaryTrees"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #带因子的二叉树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给出一个含有不重复整数元素的数组 <code>arr</code> ，每个整数 <code>arr[i]</code> 均大于 1。</p>\n",
    "\n",
    "<p>用这些整数来构建二叉树，每个整数可以使用任意次数。其中：每个非叶结点的值应等于它的两个子结点的值的乘积。</p>\n",
    "\n",
    "<p>满足条件的二叉树一共有多少个？答案可能很大，返回<strong> 对 </strong><code>10<sup>9</sup> + 7</code> <strong>取余</strong> 的结果。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> <code>arr = [2, 4]</code>\n",
    "<strong>输出:</strong> 3\n",
    "<strong>解释:</strong> 可以得到这些二叉树: <code>[2], [4], [4, 2, 2]</code></pre>\n",
    "\n",
    "<p><strong>示例 2:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> <code>arr = [2, 4, 5, 10]</code>\n",
    "<strong>输出:</strong> <code>7</code>\n",
    "<strong>解释:</strong> 可以得到这些二叉树: <code>[2], [4], [5], [10], [4, 2, 2], [10, 2, 5], [10, 5, 2]</code>.</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= arr.length &lt;= 1000</code></li>\n",
    "\t<li><code>2 &lt;= arr[i] &lt;= 10<sup>9</sup></code></li>\n",
    "\t<li><code>arr</code> 中的所有值 <strong>互不相同</strong></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [binary-trees-with-factors](https://leetcode.cn/problems/binary-trees-with-factors/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [binary-trees-with-factors](https://leetcode.cn/problems/binary-trees-with-factors/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[2,4]', '[2,4,5,10]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "### Bottom up dp, but too slow\n",
    "# class Solution:\n",
    "#     def numFactoredBinaryTrees(self, A: List[int]) -> int:\n",
    "#         A.sort()\n",
    "#         res = [1] * len(A) # initilize the answer ending with root A[i] to 1\n",
    "#         for i in range(len(A)):\n",
    "#             for j in range(i):\n",
    "#                 for k in range(j, i):\n",
    "#                     if A[j] * A[k] > A[i]: \n",
    "#                         continue\n",
    "#                     if A[j] * A[k] == A[i]: # if can be product of two number\n",
    "#                         if j == k:\n",
    "#                             res[i] += res[j] * res[k]\n",
    "#                         else:\n",
    "#                             res[i] += res[j] * res[k] * 2\n",
    "#             # print(res)\n",
    "#         return sum(res) % (10**9+7)\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def numFactoredBinaryTrees(self, A):\n",
    "            dp = {}\n",
    "            for a in sorted(A):\n",
    "                dp[a] = sum(dp[b] * dp.get(a / b, 0) for b in dp if a % b == 0) + 1\n",
    "            return sum(dp.values()) % (10**9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "mmm=1000000007\n",
    "class Solution:\n",
    "    def numFactoredBinaryTrees(self, A):\n",
    "        \"\"\"\n",
    "        :type A: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        A.sort()\n",
    "        res,rr=[1],1\n",
    "        for i in range(1,len(A)):\n",
    "            tmp=1\n",
    "            l,r=0,i-1\n",
    "            while l<=r:\n",
    "                if A[l]*A[r]==A[i]:\n",
    "                    tmp+=res[l]*res[r]*(1+(l!=r))\n",
    "                    l+=1\n",
    "                    r-=1\n",
    "                elif A[l]*A[r]<A[i]:\n",
    "                    l+=1\n",
    "                else:\n",
    "                    r-=1\n",
    "            tmp%=mmm\n",
    "            res.append(tmp)\n",
    "            rr+=tmp\n",
    "        return rr%mmm"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "mmm=1000000007\n",
    "class Solution:\n",
    "    def numFactoredBinaryTrees(self, A):\n",
    "        \"\"\"\n",
    "        :type A: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        A.sort()\n",
    "        res=[1]\n",
    "        for i in range(1,len(A)):\n",
    "            tmp=1\n",
    "            l,r=0,i-1\n",
    "            while l<=r:\n",
    "                if A[l]*A[r]==A[i]:\n",
    "                    tmp+=res[l]*res[r]*(1+(l!=r))\n",
    "                    l+=1\n",
    "                    r-=1\n",
    "                elif A[l]*A[r]<A[i]:\n",
    "                    l+=1\n",
    "                else:\n",
    "                    r-=1\n",
    "            res.append(tmp%mmm)\n",
    "        # print(res)\n",
    "        return sum(res)%mmm"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numFactoredBinaryTrees(self, A: List[int]) -> int:\n",
    "        # 根节点会越来越大,等于左右节点的乘积,我们进行升序排序\n",
    "        # dp[i]表示以A[i]数字为root的解的可能数\n",
    "        # dp[i] = sum(dp[a] * dp[b])\n",
    "        # res = sum(dp)\n",
    "\n",
    "        # [2,4,5,10] dp[2]=1 dp[4]=2 dp[5]=1 dp[10]=1+1+1=3\n",
    "        # [2,4] dp[2]=1 dp[4]=2=dp[2]*dp[2]而不是相加,dp[4]左节点1中可能,右节点1种,总的可能性1*1\n",
    "        k_mod = 10 ** 9 + 7\n",
    "        A.sort()\n",
    "        from collections import defaultdict\n",
    "        dp = defaultdict(int)\n",
    "        for i in range(len(A)):\n",
    "            # 当前数字A[i]默认解的个数就是其本身1种, A[i]类似于c, A[j]类似于左节点a,求b\n",
    "            dp[A[i]] = 1\n",
    "            for j in range(i):\n",
    "                if A[i] % A[j] == 0 and A[i] // A[j] in dp:\n",
    "                    dp[A[i]] += (dp[A[j]] * dp[A[i] // A[j]]) % k_mod\n",
    "        # 统计每个dp[i]解的可能数\n",
    "        return sum(dp.values()) % k_mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numFactoredBinaryTrees(self, A: List[int]) -> int:\n",
    "        # 根节点会越来越大,等于左右节点的乘积,我们进行升序排序\n",
    "        # dp[i]表示以A[i]数字为root的解的可能数\n",
    "        # dp[i] = sum(dp[a] * dp[b])\n",
    "        # res = sum(dp)\n",
    "        k_mod = 10 ** 9 + 7\n",
    "        A.sort()\n",
    "        from collections import defaultdict\n",
    "        dp = defaultdict(int)\n",
    "        for i in range(len(A)):\n",
    "            # 当前数字A[i]默认解的个数就是其本身1种, A[i]类似于c, A[j]类似于左节点a,求b\n",
    "            dp[A[i]] = 1\n",
    "            for j in range(i):\n",
    "                if A[i] % A[j] == 0 and A[i] // A[j] in dp:\n",
    "                    dp[A[i]] += (dp[A[j]] * dp[A[i] // A[j]]) % k_mod\n",
    "        # 统计每个dp[i]解的可能数\n",
    "        return sum(dp.values()) % k_mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numFactoredBinaryTrees(self, A: List[int]) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        N = len(A)\n",
    "        A.sort()\n",
    "        dp = [1] * N\n",
    "        index = {x: i for i, x in enumerate(A)}\n",
    "        for i, x in enumerate(A):\n",
    "            for j in range(i):\n",
    "                if x % A[j] == 0: #A[j] will be left child\n",
    "                    right = x / A[j]\n",
    "                    if right in index:\n",
    "                        dp[i] += dp[j] * dp[index[right]]\n",
    "                        dp[i] %= MOD\n",
    "\n",
    "        return sum(dp) % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numFactoredBinaryTrees(self, A: List[int]) -> int:\n",
    "        num = set(A)\n",
    "        memo, mod = {}, int(10 ** 9 + 7)\n",
    "        A.sort()\n",
    "        ans = 0\n",
    "        for i in range(len(A)):\n",
    "            cur = 1\n",
    "            for j in range(i):\n",
    "                if A[i] % A[j] == 0 and A[i] // A[j] in num:\n",
    "                    cur += memo[A[j]] * memo[A[i]//A[j]]\n",
    "            memo[A[i]] = cur\n",
    "            ans = (ans + cur) % mod\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numFactoredBinaryTrees(self, A: List[int]) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        N = len(A)\n",
    "        A.sort()\n",
    "        dp = [1] * N\n",
    "        index = {x: i for i, x in enumerate(A)}\n",
    "        for i, x in enumerate(A):\n",
    "            for j in range(i):\n",
    "                if x % A[j] == 0: #A[j] will be left child\n",
    "                    right = x / A[j]\n",
    "                    if right in index:\n",
    "                        dp[i] += dp[j] * dp[index[right]]\n",
    "                        dp[i] %= MOD\n",
    "\n",
    "        return sum(dp) % MOD\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numFactoredBinaryTrees(self, A: List[int]) -> int:\n",
    "        # 每个节点的值都大于1，即不会存在无赖节点\n",
    "        # 特点1：二叉树的顶部节点肯定是二叉树中最大的节点\n",
    "        # 特点2：节点顺序互换可以理解为两个不同的二叉树\n",
    "        # 简单办法：逐个节点遍历，如果可以在数组中找到它的因子就可以继续生成新的，并且如果两个叶节点的数值不相等就可以生成不同的二叉树\n",
    "        # 进阶办法：\n",
    "        # 1. 对数组进行排序\n",
    "        # 2. 从小到大进行计算，这样可以避免算过的元素重复进行计算\n",
    "        A = sorted(A)\n",
    "        mp = {}\n",
    "        res = 0\n",
    "        for i in range(len(A)):            \n",
    "            mp[A[i]] = 1\n",
    "            # 开始遍历比A[i]小的元素\n",
    "            for j in range(i):\n",
    "                p = A[i] // A[j]  # 商\n",
    "                q = A[i] % A[j]   # 余数\n",
    "                # 避免重复计算\n",
    "                # 因此之前循环的时候小于A[j]的元素已经被计算过了(*2)\n",
    "                # 如果再算一遍数值就会偏大\n",
    "                if p < A[j]:\n",
    "                    break\n",
    "                if q == 0 and p in mp.keys():\n",
    "                    # 两个叶节点相同，只计算一次\n",
    "                    if p == A[j]:\n",
    "                        mp[A[i]] += mp[p] * mp[A[j]]\n",
    "                    else:\n",
    "                        mp[A[i]] += mp[p] * mp[A[j]] * 2\n",
    "            res += mp[A[i]]\n",
    "        return int(res % (1E9+7))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numFactoredBinaryTrees(self, A: List[int]) -> int:\n",
    "        MOD = 10**9+7\n",
    "        len_ = len(A)\n",
    "        A.sort()\n",
    "        index = {x:i for i,x in enumerate(A)}\n",
    "        dp = [1]*len_\n",
    "        for i,x in enumerate(A):\n",
    "            for j in range(i):\n",
    "                if x % A[j] == 0:\n",
    "                    right = A[i] / A[j]\n",
    "                    if right in A:\n",
    "                        dp[i] += dp[j]*dp[index[right]]\n",
    "                        dp[i] %= MOD\n",
    "        return sum(dp)%MOD\n",
    "\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def numFactoredBinaryTrees(self, A: List[int]) -> int:\r\n",
    "        ans = 0\r\n",
    "        dic = {}\r\n",
    "        A.sort()\r\n",
    "        print(A)\r\n",
    "        for num in A:\r\n",
    "            value = 1\r\n",
    "            for key in dic.keys():\r\n",
    "                value += dic[key] * dic.get(num / key, 0)\r\n",
    "            dic[num] = value\r\n",
    "            ans += value\r\n",
    "        return ans % (10 ** 9 + 7)\r\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numFactoredBinaryTrees(self, A: List[int]) -> int:\n",
    "        LEN = len(A)\n",
    "        if LEN <= 1: return LEN\n",
    "        A.sort()\n",
    "        dp = [1 for _ in range(LEN)]\n",
    "        mp = {num: [] for num in A}\n",
    "        for i in range(LEN):\n",
    "            for j in range(i, LEN):\n",
    "                k = A[i] * A[j]\n",
    "                if k in mp:\n",
    "                    mp[k].append([i, j])\n",
    "        for i, a in enumerate(A):\n",
    "            for x, y in mp[a]:\n",
    "                delta = dp[x] * dp[y]\n",
    "                if x != y: delta *= 2\n",
    "                dp[i] += delta\n",
    "        return sum(dp) % (10 ** 9 + 7)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def numFactoredBinaryTrees(self, A):\n",
    "        \"\"\"\n",
    "        :type A: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        mx = max(A)\n",
    "        AA = set(A)\n",
    "        m = 10 ** 9 + 7\n",
    "        d = {}\n",
    "        for a in A:\n",
    "            for b in A:\n",
    "                p = a * b\n",
    "                if p > mx or p not in AA: continue\n",
    "                if p not in d:\n",
    "                    d[p] = set()\n",
    "                d[p].add((a, b))\n",
    "        A.sort()\n",
    "        res = {}\n",
    "        r = 0\n",
    "        for a in A:\n",
    "            v = 1\n",
    "            if a in d:\n",
    "                s = d[a]\n",
    "                for x, y in s:\n",
    "                    v += res[x] * res[y]\n",
    "                    v = v % m\n",
    "            res[a] = v % m\n",
    "            r += res[a]\n",
    "        return r % m"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numFactoredBinaryTrees(self, A: List[int]) -> int:\n",
    "        A.sort()\n",
    "        s = set(A)\n",
    "        @lru_cache(None)\n",
    "        def cal(i):\n",
    "            res = 1\n",
    "            for ii in A:\n",
    "                if ii >= i:\n",
    "                    break\n",
    "                if i % ii == 0 and i // ii in s:\n",
    "                    res += cal(ii) * cal(i//ii)\n",
    "            # print(i,res)\n",
    "            return res % 1000000007\n",
    "        res = 0\n",
    "        for i in A:\n",
    "            res += cal(i)\n",
    "        return res % 1000000007\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numFactoredBinaryTrees(self, arr: List[int]) -> int:\n",
    "#         arr.sort()\n",
    "#         dp = collections.defaultdict(int)\n",
    "#         for i in range(len(arr)):\n",
    "#             dp[arr[i]] = 1\n",
    "#             for j in range(i):\n",
    "#                 if arr[i]%arr[j]==0 and int(arr[i]/arr[j]) in dp:\n",
    "#                     dp[arr[i]] += dp[arr[j]] * dp[int(arr[i]/arr[j])]           \n",
    "#         return sum(dp.values())%(10**9+7)\n",
    "                \n",
    "    \n",
    "        arr.sort()\n",
    "        dp = [1] * len(arr)\n",
    "        for i in range(len(arr)):\n",
    "            dp[i] = 1\n",
    "            for j in range(i):\n",
    "                if arr[i]%arr[j]==0 and int(arr[i]/arr[j]) in arr:\n",
    "                    dp[i] += dp[j] * dp[arr.index(int(arr[i]/arr[j]))]           \n",
    "        return sum(dp)%(10**9+7)\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numFactoredBinaryTrees(self, A: List[int]) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        N = len(A)\n",
    "        A.sort()\n",
    "        dp = [1] * N\n",
    "        index = {x: i for i, x in enumerate(A)}\n",
    "        for i, x in enumerate(A):\n",
    "            for j, y in enumerate(A):\n",
    "                if y >= x:\n",
    "                    break\n",
    "                r = x / y\n",
    "                if r in index:\n",
    "                    dp[i] += dp[index[r]] * dp[j]\n",
    "        return sum(dp) % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def numFactoredBinaryTrees(self, A):\n",
    "        MOD = 10 ** 9 + 7\n",
    "        N = len(A)\n",
    "        A.sort()\n",
    "        dp = [1] * N\n",
    "        index = {x: i for i, x in enumerate(A)}\n",
    "        for i, x in enumerate(A):\n",
    "            for j in range(i):\n",
    "                if x % A[j] == 0:  # A[j] will be left child\n",
    "                    right = x // A[j]\n",
    "                    if right in index:\n",
    "                        dp[i] += dp[j] * dp[index[right]]\n",
    "                        dp[i] %= MOD\n",
    "\n",
    "        return sum(dp) % MOD\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numFactoredBinaryTrees(self, A: List[int]) -> int:\n",
    "        LEN = len(A)\n",
    "        if LEN <= 1: return LEN\n",
    "        A.sort()\n",
    "        dp = [1 for _ in range(LEN)]\n",
    "        mp = {num: [] for num in A}\n",
    "        for i in range(LEN):\n",
    "            for j in range(i, LEN):\n",
    "                k = A[i] * A[j]\n",
    "                if k in mp:\n",
    "                    mp[k].append([i, j])\n",
    "        for i, a in enumerate(A):\n",
    "            for x, y in mp[a]:\n",
    "                delta = dp[x] * dp[y]\n",
    "                if x != y: delta *= 2\n",
    "                dp[i] += delta\n",
    "        return sum(dp) % (10 ** 9 + 7)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numFactoredBinaryTrees(self, A: List[int]) -> int:\n",
    "        LEN = len(A)\n",
    "        if LEN <= 1: return LEN\n",
    "        A.sort()\n",
    "        dp = [1 for _ in range(LEN)]\n",
    "        mp = {num: [] for num in A}\n",
    "        for i in range(LEN):\n",
    "            for j in range(i, LEN):\n",
    "                k = A[i] * A[j]\n",
    "                if k in mp:\n",
    "                    mp[k].append([i, j])\n",
    "        for i, a in enumerate(A):\n",
    "            for x, y in mp[a]:\n",
    "                delta = dp[x] * dp[y]\n",
    "                if x != y: delta *= 2\n",
    "                dp[i] += delta\n",
    "        return sum(dp) % (10 ** 9 + 7)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numFactoredBinaryTrees(self, arr: List[int]) -> int:\n",
    "        # 动态规划  +  双指针\n",
    "        n = len(arr)\n",
    "        # 排序好的数组 二分查找 最快 双指针应用\n",
    "        arr = sorted(arr)\n",
    "        dp = [1] * n\n",
    "        res,mod = 0,10**9+7\n",
    "        for i in range(n):\n",
    "            left , right = 0,i-1\n",
    "            while left <= right:# 有平方的情况\n",
    "                while right >= left and arr[left] * arr[right] > arr[i]:\n",
    "                    right -= 1\n",
    "                if right >= left and arr[left] * arr[right] == arr[i]:\n",
    "                    if right != left:\n",
    "                        dp[i] = (dp[i] + dp[right] * dp[left] * 2) % mod\n",
    "                    else:\n",
    "                        dp[i] = (dp[i] + dp[right] * dp[left]) % mod\n",
    "                left += 1\n",
    "            res = (res + dp[i]) % mod\n",
    "        return res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numFactoredBinaryTrees(self, arr: List[int]) -> int:\n",
    "        N=len(arr)\n",
    "        arr.sort()\n",
    "        seen=dict()\n",
    "        for i in range(N):\n",
    "            seen[arr[i]]=i\n",
    "        dp=[1]*N\n",
    "        mod=10**9+7\n",
    "        ans=0\n",
    "        \n",
    "        for i in range(N):\n",
    "            for j in range(i):\n",
    "                if arr[i]%arr[j]==0 and arr[i]//arr[j] in seen:\n",
    "                    dp[i]=(dp[i]+dp[j]*dp[seen[arr[i]//arr[j]]])%mod\n",
    "            ans=(ans+dp[i])%mod\n",
    "        return ans \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numFactoredBinaryTrees(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        arr = sorted(arr)\n",
    "        dp = [1] * n\n",
    "        res, mod = 0, 10**9 + 7\n",
    "        for i in range(n):\n",
    "            left, right = 0, i - 1\n",
    "            while left <= right:\n",
    "                while right >= left and arr[left] * arr[right] > arr[i]:\n",
    "                    right -= 1\n",
    "                if right >= left and arr[left] * arr[right] == arr[i]:\n",
    "                    if right != left:\n",
    "                        dp[i] = (dp[i] + dp[left] * dp[right] * 2) % mod\n",
    "                    else:\n",
    "                        dp[i] = (dp[i] + dp[left] * dp[right]) % mod\n",
    "                left += 1\n",
    "            res = (res + dp[i]) % mod\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def numFactoredBinaryTrees(self, arr: List[int]) -> int:\n",
    "        \n",
    "        tumb=10**9+7\n",
    "        res=0 #这是返回结果，二叉树的数量\n",
    "        factorMap=dict() #这是用来快速查找的散列表\n",
    "        singleFactor=[0 for i in range(1000)]\n",
    "        arr=sorted(arr,reverse=False) \n",
    "        length=len(arr)\n",
    "        index=0\n",
    "        while index<length:\n",
    "            factorMap[arr[index]]=index\n",
    "            i=0\n",
    "            while i<index:\n",
    "                if arr[index]%arr[i]==0:\n",
    "                    temp=int(arr[index]/arr[i])\n",
    "                    if temp in factorMap:\n",
    "                        singleFactor[index]+=singleFactor[i]*singleFactor[factorMap[temp]]\n",
    "                        singleFactor[index]=singleFactor[index]%tumb\n",
    "                i+=1\n",
    "            singleFactor[index]+=1\n",
    "            \n",
    "            pass\n",
    "            index+=1\n",
    "        pass\n",
    "        for i in range(length):\n",
    "            res+=singleFactor[i]\n",
    "            res%=tumb\n",
    "        print(singleFactor)\n",
    "        return res\n",
    "\n",
    "    \n",
    "\n",
    "\n",
    "\n",
    "#  $ sudo mariadb-install-db --user=mysql --basedir=/usr --datadir=/var/lib/mysql\n",
    "# Installing MariaDB/MySQL system tables in '/var/lib/mysql' ...\n",
    "# OK\n",
    "\n",
    "# To start mariadbd at boot time you have to copy\n",
    "# support-files/mariadb.service to the right place for your system\n",
    "\n",
    "\n",
    "# Two all-privilege accounts were created.\n",
    "# One is root@localhost, it has no password, but you need to\n",
    "# be system 'root' user to connect. Use, for example, sudo mysql\n",
    "# The second is mysql@localhost, it has no password either, but\n",
    "# you need to be the system 'mysql' user to connect.\n",
    "# After connecting you can set the password, if you would need to be\n",
    "# able to connect as any of these users with a password and without sudo\n",
    "\n",
    "# See the MariaDB Knowledgebase at https://mariadb.com/kb\n",
    "\n",
    "# You can start the MariaDB daemon with:\n",
    "# cd '/usr' ; /usr/bin/mariadb-safe --datadir='/var/lib/mysql'\n",
    "\n",
    "# You can test the MariaDB daemon with mariadb-test-run.pl\n",
    "# cd '/usr/mariadb-test' ; perl mariadb-test-run.pl\n",
    "\n",
    "# Please report any problems at https://mariadb.org/jira\n",
    "\n",
    "# The latest information about MariaDB is available at https://mariadb.org/.\n",
    "\n",
    "# Consider joining MariaDB's strong and vibrant community:\n",
    "# https://mariadb.org/get-involved/\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numFactoredBinaryTrees(self, arr: List[int]) -> int:\n",
    "        tmp_list = []\n",
    "        set_arr = set(arr)\n",
    "        num_dict = {i:1 for i in arr}\n",
    "        print(num_dict)\n",
    "        for i in range(len(arr)):\n",
    "            for j in range(i,len(arr)):\n",
    "                if arr[i]*arr[j] in set_arr:\n",
    "                    tmp_list.append((i,j,arr[i]*arr[j]))\n",
    "        sort_list = sorted(tmp_list,key = lambda x:x[2])\n",
    "        print(sort_list)\n",
    "        for i in sort_list:\n",
    "            if i[0] == i[1]:\n",
    "                num_dict[i[2]] += (num_dict[arr[i[0]]]*num_dict[arr[i[1]]])\n",
    "            else:\n",
    "                num_dict[i[2]] += (num_dict[arr[i[0]]]*num_dict[arr[i[1]]]*2)\n",
    "        return sum(num_dict.values())% (10**9 + 7)\n",
    "\n",
    "        # def cal(num_dict,list1):\n",
    "        #     have_num = list1[-1]\n",
    "        #     for i in range(len(list1)):\n",
    "        #         for j in range(i,len(list1)):\n",
    "        #             if list1[i]*list1[j] == have_num:\n",
    "        #                 if i == j:\n",
    "        #                     num_dict[list1[i]*list1[j]] += (num_dict[list1[i]]*num_dict[list1[j]])\n",
    "        #                 else:\n",
    "        #                     num_dict[list1[i]*list1[j]] += ((num_dict[list1[i]]*num_dict[list1[j]])*2)\n",
    "        \n",
    "        # arr = sorted(arr)\n",
    "        # num_dict = {i:1 for i in arr}\n",
    "        # for i in range(1,len(arr)):\n",
    "        #     cal(num_dict,arr[:i+1])\n",
    "        # return sum(num_dict.values())% (10**9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numFactoredBinaryTrees(self, arr: List[int]) -> int:\n",
    "        mod = 10 ** 9 + 7\n",
    "        arr.sort()\n",
    "        n = len(arr)\n",
    "        dic = set(arr)\n",
    "\n",
    "        @cache\n",
    "        def dfs(i) :\n",
    "            res = 1\n",
    "            for k in arr :\n",
    "                if i % k == 0 and  i // k in dic :\n",
    "                    res += dfs(k) * dfs(i // k)\n",
    "            return res % mod\n",
    "        \n",
    "        ans = 0\n",
    "        for k in arr :\n",
    "            ans = (ans + dfs(k))\n",
    "\n",
    "        return ans % mod\n",
    "                \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numFactoredBinaryTrees(self, arr: List[int]) -> int:\n",
    "        dic=set(arr)\n",
    "        ans=0\n",
    "        MOD=10**9+7\n",
    "        memo={}\n",
    "        \n",
    "        def dfs(val):\n",
    "            if val in memo:\n",
    "                return memo[val]\n",
    "            res=1\n",
    "            for i in arr:\n",
    "                if val%i==0 and val//i in dic:\n",
    "                    res+=dfs(i)*dfs(val//i)\n",
    "            memo[val]=res\n",
    "            return res\n",
    "\n",
    "        for i in arr:\n",
    "            ans+=dfs(i)\n",
    "        return ans%MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numFactoredBinaryTrees(self, arr: List[int]) -> int:\n",
    "        s = set(arr)\n",
    "\n",
    "        # 获取以val为根的二叉树的数量\n",
    "        @cache\n",
    "        def dfs(val):\n",
    "            res = 1\n",
    "            for x in arr:\n",
    "                if val % x == 0 and val // x in s:\n",
    "                    res += dfs(val // x) * dfs(x)\n",
    "            return res\n",
    "\n",
    "        return sum(dfs(x) for x in arr) % (10 ** 9  +  7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numFactoredBinaryTrees(self, arr: List[int]) -> int:\n",
    "        arr.sort()\n",
    "        idx = {x:i for i,x in enumerate(arr)}\n",
    "        @cache\n",
    "        def dfs(i):\n",
    "            ans = 1\n",
    "            val = arr[i]\n",
    "            for j in range(i):\n",
    "                x = arr[j]\n",
    "                if val % x == 0 and val/x in idx:\n",
    "                    ans += dfs(j)*dfs(idx[val/x])\n",
    "            return ans\n",
    "        return sum(dfs(i) for i in range(len(arr)))%(10**9+7)\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
